import java.util.Stack;

/**
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
 */
public class Solution31 {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null) {
            return false;
        }

        if (pushA.length != popA.length) {
            return false;
        }

        Stack<Integer> stack = new Stack<>();
        int currentPushA = 0;
        int currentPopA = 0;
        while (currentPopA < popA.length) {
            if (currentPushA >= pushA.length) {
                // push完了 检验pop出来的是否正确
                if (stack.pop() == popA[currentPopA]) {
                    currentPopA++;
                } else {
                    return false;
                }
            } else {
                if (pushA[currentPushA] != popA[currentPopA]) {
                    stack.push(pushA[currentPushA]);
                    currentPushA++;
                } else {
                    currentPushA++;
                    currentPopA++;
                }
            }
        }

        return true;
    }
}
